package com.sicheng.lc.周赛.分类.并差集;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/26 10:13
 */
public class 统计无向图中无法互相到达点对数 {
    //https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/
    int[] p;
    int[] cnt;
    long total;

    int find(int x) {
        if (p[x] == x)
            return p[x];
        return p[x] = find(p[x]);
    }

    void init(int n) {
        total = (long) n * (n - 1) >> 1;
        p = new int[n];
        cnt = new int[n];
        for (int i = 0; i < n; i++) {
            cnt[i] = 1;
            p[i] = i;
        }
    }

    void union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            total -= (long) cnt[pa] * cnt[pb];
            if (pb > pa) {
                int t = pa;
                pa = pb;
                pb = t;
            }
            p[pb] = pa;
            cnt[pa] += cnt[pb];
        }
    }

    public long countPairs(int n, int[][] edges) {
        if (n < 2)
            return 0;
        if (edges.length == 0)
            return (long) (n - 1) * n >> 1;
        init(n);
        for (int[] edge : edges) {
            union(edge[0], edge[1]);
        }

        return total;
    }

    public static void main(String[] args) {
        统计无向图中无法互相到达点对数 s = new 统计无向图中无法互相到达点对数();
        System.out.println(s.countPairs(12, new int[][]{}));
    }
}
